package org.example.myleet.floyd;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;

import java.util.Arrays;

public class FloydSolution {
    /**
     * 2959【位运算+枚举+Floyd最短路】关闭分部的可行集合数目
     */
    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        int INF = 0x3f3f3f3f;
        //重建图，两点之间的连接路径使用最小的，重复的更大的忽略掉
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
        for (int[] road : roads) {
            int i = road[0], j = road[1];
            graph[i][j] = Math.min(graph[i][j], road[2]);
            graph[j][i] = Math.min(graph[j][i], road[2]);
        }
        int status = 0, endStatus = (1 << n) - 1, answer = 0;
        int[][] g = new int[n][n];
        while (status <= endStatus) {
            //floyd算法查找两个点之间的最短距离
            //floyd-1: 初始化距离矩阵
            for (int i = 0; i < n; ++i) {
                Arrays.fill(g[i], INF);
            }
            for (int i = 0; i < n; ++i) {
                if ((status & (1 << i)) != 0) {
                    for (int j = 0; j < n; ++j) {
                        if ((status & (1 << j)) != 0) {
                            if (i == j) {
                                g[i][j] = 0;
                            } else {
                                g[i][j] = Math.min(g[i][j], graph[i][j]);
                                g[j][i] = Math.min(g[j][i], graph[j][i]);
                            }
                        }
                    }
                }
            }
            //floyd-2: 以每个点i为中介点更新距离矩阵
            for (int i = 0; i < n; ++i) {
                if ((status & (1 << i)) != 0) {
                    for (int j = 0; j < n; ++j) {
                        if (i != j && (status & (1 << j)) != 0) {
                            for (int k = 0; k < n; ++k) {
                                if (i != k && (status & (1 << k)) != 0) {
                                    if (g[j][k] > g[j][i] + g[k][i]) {
                                        g[j][k] = g[j][i] + g[k][i];
                                        g[k][j] = g[j][i] + g[k][i];
                                    }
                                }
                            }
                        }
                    }
                }
            }
            //验证最终整个距离矩阵中是否有超过maxDistance的距离
            boolean legal = true;
            tag:
            for (int i = 0; i < n; ++i) {
                if ((status & (1 << i)) == 0) continue;
                for (int j = 0; j < n; ++j) {
                    if ((status & (1 << j)) == 0) continue;
                    if (g[i][j] > maxDistance) {
                        legal = false;
                        break tag;
                    }
                }
            }
            if (legal) ++answer;
            ++status;
        }
        return answer;
    }

    public static void main(String[] args) {
        FloydSolution solution = new FloydSolution();
        Assert.isTrue(5 == solution.numberOfSets(3, 5, Parser.parse("[[0,1,2],[1,2,10],[0,2,10]]")));
    }
}
